﻿#define _CRT_SECURE_NO_WARNINGS 1
//外观数列 (medium): https://leetcode.cn/problems/count-and-say/
class Solution {
public:
    string countAndSay(int n) {
        string s = "1";
        int count = 0;
        while (--n)
        {
            string str;   //把 s 转化为 str
            int cur = 0, prev = 0;
            for (cur = 0, prev = 0; cur < s.size(); cur++)
            {
                if (s[cur] != s[prev])
                {
                    count = cur - prev;
                    str += count + '0';  //数字变字符
                    str += s[prev];
                    prev = cur;
                }
            }
            count = cur - prev;
            str += count + '0';
            str += s[prev];
            s = str;
        }

        return s;
    }
};

//数⻘蛙（medium）:https://leetcode.cn/problems/minimum-number-of-frogs-croaking/submissions/573653443/
//v1:
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        unordered_map<char, int> hash;   //unordered_map<char int> hash;
        for (auto x : croakOfFrogs)
        {
            if (x == 'c')
            {
                if (hash['k']) { hash['k']--; hash['c']++; }
                else             hash['c']++;
            }
            else if (x == 'r')
            {
                if (hash['c']) { hash['c']--;  hash['r']++; }
                else              return -1;
            }
            else if (x == 'o')
            {
                if (hash['r']) { hash['r']--;  hash['o']++; }
                else              return -1;
            }
            else if (x == 'a')
            {
                if (hash['o']) { hash['o']--;  hash['a']++; }
                else              return -1;
            }
            else if (x == 'k')
            {
                if (hash['a']) { hash['a']--;  hash['k']++; }
                else              return -1;
            }
        }
        if (hash['c'] || hash['r'] || hash['o'] || hash['a'])
        {
            return -1;
        }
        else
        {
            return hash['k'];
        }
    }
};
//v2:
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        //上一版是  int 和 croak中的字符 的哈希表 ，又因为要牵涉到前屈字符的int的问题，所以上版有很多if
        //这一版 用的是 croak中的字符的下标 和 int 的哈希表(可以用数组代替），另外还要加一个 下标 和 字符 的哈希表

        //搞一个下标 和 字符 的哈希表
        string t = "croak";
        int n = t.size();
        unordered_map<char, int> inder;
        for (int i = 0; i < t.size(); i++)  //inder[字符]=下标；
        {
            inder[t[i]] = i;
        }


        vector<int> hash(n);
        for (auto ch : croakOfFrogs)  //遍历到一个数，先算出它的下标，然后看它的上一个下标的int,再进行加加减减
        {
            int id = inder[ch];   //该字符下标
            if (id == 0)  //下标为0，是第一个，看最后一个的int
            {
                if (hash[n - 1]) { hash[n - 1]--; }
                hash[0]++;
            }
            else
            {
                if (hash[id - 1]) { hash[id - 1]--; hash[id]++; }
                else   return -1;
            }
        }
        for (int i = 0; i < n - 1; i++)
        {
            if (hash[i])   return -1;
        }
        return hash[n - 1];
    }
};